package com.lihepeng.leecode.recursive;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号的生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class Solution22 {
    List<String> result = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        recursive(n,n,new StringBuffer());
        return result;
    }
    private void recursive(int left,int right,StringBuffer stringBuffer){
        if (right<left) {
            return;
        }
        if (left<0 || right <0) {
            return;
        }
        if (left ==right && left ==0) {
            result.add(stringBuffer.toString());
        }
        // 尝试放一个左括号
        stringBuffer.append("(");
        recursive(left-1,right,stringBuffer);
        // 撤销选择
        stringBuffer.deleteCharAt(stringBuffer.length()-1);
        stringBuffer.append(")");
        recursive(left,right-1,stringBuffer);
        stringBuffer.deleteCharAt(stringBuffer.length()-1);
    }
    @Test
    public void runTest(){
        List<String> strings = this.generateParenthesis(3);
        System.out.println(strings);
    }
}
